import java.util.ArrayList;
import java.util.Arrays;

//三数之和，且三元组不能重复，三数之和为0
public class sumOfThreeNumber {
    public ArrayList sum(int[] nums,ArrayList list){
        Arrays.sort(nums);//先进行排序
        //使用双指针法
        for(int i=0;i<nums.length;i++){//第一个元素的位置
            if (nums[i]>0){//排序后，因为如果第一个都大于0了，其他的肯定都是大于0的
                return list;
            }
            //去重，因为三元组不能重复
            if(i>0&&nums[i-1]==nums[i]){//如果和第一个元素和前面一个元素相同，肯定已经处理过了，所以直接跳过
                continue;//老是将--操作和-1操作搞混了，这两个是天差地别的操作啊
            }

            int left = i+1;
            int right = nums.length-1;
            while (left<right){//寻找第二个和第三个元素
                System.out.println("yes");
                if(nums[i]+nums[left]+nums[right]>0) right--;
                else if(nums[i]+nums[left]+nums[right]<0) left++;
                else {//这里说明找到了一个解
                    list.add(new int[]{nums[i],nums[left],nums[right]});
                    //这里又快要开始去重，去除相同的元素
                    while (left<right&&nums[left]==nums[left+1]) left++;
                    while (left<right&&nums[right]==nums[right-1]) right--;
                    //去重之后就得再移动到下一个位置
                    left++;
                    right--;
                }
            }
        }
        return list;
    }
    public static void main(String[] args) {
        ArrayList<int[]> list = new ArrayList<>();//动态数组，用来存放结果
        var main = new sumOfThreeNumber();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        ArrayList res = main.sum(nums,list);
        for (int[] array:list){
            System.out.println(Arrays.toString(array));
        }
    }
}
